/*
 * SchulzeEvaluator.java
 *
 * Copyright (C) 2014 Fabian Wenzelmann
 *
 * This file is part of stura_voting.
 *
 * stura_voting is free software: you
 * can redistribute it and/or modify it under the terms of the
 * GNU General Public License as published by the Free Software Foundation,
 * either version 3 of the License, or (at your option) any later version.
 *
 * stura_voting is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
 * Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with stura_voting.
 *
 * If not, see <http://www.gnu.org/licenses/>.
 */

package de.stura.schulze;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collections;
import java.util.Comparator;

// TODO: take care that no option appears more than once?
public class SchulzeEvaluator {
    private ArrayList<ArrayList<SchulzeVote>> votes;
    int numChoices;
    int[][] lastD;
    int[][] lastP;
    ArrayList<String> choiceNames;
    
    public SchulzeEvaluator(int numChoices) {
        this(new String[numChoices]);
    }
    
    public SchulzeEvaluator(String[] choiceNames) {
        this.votes = new ArrayList<ArrayList<SchulzeVote>>();
        this.numChoices = choiceNames.length + 1;
        lastD = null;
        lastP = null;
        this.choiceNames = new ArrayList<String>(choiceNames.length + 1);
        for (String s : choiceNames) {
            this.choiceNames.add(s);
        }
        this.choiceNames.add("Dagegen");
    }
    
    public void addVote(ArrayList<SchulzeVote> vote) {
        votes.add(vote);
    }

    private int[][] computeD() {
        int[][] d = new int[numChoices][];
        for (int i = 0; i < numChoices; ++i) {
            d[i] = new int[numChoices];
        }
        for (ArrayList<SchulzeVote> vote : votes) {
            int i = 0;
            while (i < vote.size()) {
                SchulzeVote voteI = vote.get(i);
                int lastPos = voteI.getPosition();
                int j = i + 1;
                while (j < vote.size()) {
                    SchulzeVote voteJ = vote.get(j);
                    if (voteJ.getPosition() != lastPos) {
                        assert(voteJ.getPosition() > lastPos);
                        // j is ranked lower than i
                        // i.e. update d and update lastPos
                        d[voteI.getChoice()][voteJ.getChoice()]++;
                    }
                    ++j;
                }
                ++i;
            }
        }
        return d;
    }
    
    private int[][] computeP(int[][] d) {
        int[][] p = new int[numChoices][];
        for (int i = 0; i < numChoices; ++i) {
            p[i] = new int[numChoices];
        }
        // implemented as explained here <http://de.wikipedia.org/wiki/Schulze-Methode#Implementierung>
        for (int i = 0; i < numChoices; ++i) {
            for (int j = 0; j < numChoices; ++j) {
                if (i != j) {
                    if (d[i][j] > d[j][i]) {
                        p[i][j] = d[i][j];
                    } else {
                        p[i][j] = 0;
                    }
                }
            }
        }
        
        for (int i = 0; i < numChoices; ++i) {
            for (int j = 0; j < numChoices; ++j) {
                if (i != j) {
                    for (int k = 0; k < numChoices; ++k) {
                        if (i != k) {
                            if (j != k) {
                                p[j][k] = Math.max(p[j][k], Math.min(p[j][i], p[i][k]));
                            }
                        }
                    }
                }
            }
        }
        return p;
    }

    public int[][] getLastD() {
        return lastD;
    }
    
    public int[][] getLastP() {
        return lastP;
    }

    public String getLastDHTML() {
        if (lastD == null) {
            return "";
        }
        StringBuilder result = new StringBuilder("<table border=\"1\"><tr><td/>");
        for (int i = 0; i < numChoices; ++i) {
            result.append("<td>d[*, ");
            result.append(i);
            result.append("]</td>");
        }
        result.append("</tr>");
        for(int i = 0; i < numChoices; ++i) {
            result.append("<tr><td>d[");
            result.append(i);
            result.append(", *]</td>");
            for (int j = 0; j < numChoices; ++j) {
                result.append("<td>");
                if (i != j) {
                    result.append(lastD[i][j]);
                }
                result.append("</td>");
            }
            result.append("</tr>");
        }
        result.append("</table>");
        return result.toString();
    }
    
    public String getLastPHTML() {
        if (lastP == null) {
            return "";
        }
        StringBuilder result = new StringBuilder("<table border=\"1\"><tr><td/>");
        for (int i = 0; i < numChoices; ++i) {
            result.append("<td>d[*, ");
            result.append(i);
            result.append("]</td>");
        }
        result.append("</tr>");
        for(int i = 0; i < numChoices; ++i) {
            result.append("<tr><td>d[");
            result.append(i);
            result.append(", *]</td>");
            for (int j = 0; j < numChoices; ++j) {
                result.append("<td>");
                if (i != j) {
                    result.append(lastP[i][j]);
                }
                result.append("</td>");
            }
            result.append("</tr>");
        }
        result.append("</table>");
        return result.toString();
    }
    
    public ArrayList<ArrayList<Integer>> evaluate() {
        // compute d[i, j]
        int[][] d = computeD();
        int[][] p = computeP(d);
        lastD = d;
        lastP = p;
        return rankP(p);
    }
    
    // implemented as _rank_p here <https://github.com/mgp/schulze-method/blob/master/schulze.py>
    private ArrayList<ArrayList<Integer>> rankP(int[][] p) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        HashMap<Integer, ArrayList<Integer>> candidateWins = new HashMap<Integer, ArrayList<Integer>>();
        for (int i = 0; i < p.length; ++i) {
            int numWins = 0;
            for (int j = 0; j < p.length; ++j) {
                if (i != j) {
                    int candidateOneScore = p[i][j];
                    int candidateTwoScore = p[j][i];
                    if (candidateOneScore > candidateTwoScore) {
                        ++numWins;
                    }
                }
            }
            ArrayList<Integer> lst = candidateWins.get(numWins);
            if (lst == null) {
                lst = new ArrayList<Integer>();
                candidateWins.put(numWins, lst);
            }
            lst.add(i);
        }
        ArrayList<Integer> keys = new ArrayList<Integer>(candidateWins.keySet());
        Collections.sort(keys, Collections.reverseOrder());
        for (int i : keys) {
            result.add(candidateWins.get(i));
        }
        return result;
    }
    
    public ArrayList<SchulzeVote> fromString(String str) throws SchulzeParseException {
        ArrayList<SchulzeVote> res = new ArrayList<SchulzeVote>();
        str = str.trim();
        String[] split = str.split(" ");
        if (split.length !=  numChoices) {
            throw new SchulzeParseException("The number of positions in input string \"" + str +
                "\" is not equal to the number of choices (" + numChoices + ").");
        }
        for (int i = 0; i < numChoices; ++i) {
            int pos = getNum(split[i]);
            res.add(new SchulzeVote(i, pos));
        }
        Comparator<SchulzeVote> comp = new Comparator<SchulzeVote>() {
            public int compare(SchulzeVote v1, SchulzeVote v2) {
                int pos1 = v1.getPosition();
                int pos2 = v2.getPosition();
                if (pos1 < pos2) {
                    return -1;
                } else if (pos1 > pos2) {
                    return 1;
                } else {
                    return 0;
                }
            }
        };
        Collections.sort(res, comp);
        return res;
    }

    private int getNum(String str) throws SchulzeParseException {
        try {
            int result = Integer.parseInt(str.trim());
            if (result < 0 || result > numChoices) {
                throw new SchulzeParseException("Invalid number '" + result + "'.\nMust be >= 0 and < than the number of choices (" + numChoices + ").");
            }
            return result - 1;
        } catch (NumberFormatException e) {
            throw new SchulzeParseException("Can't parse input as integer.", e);
        }
    }

    // TODO: Frage: für 2/3 Mehrheit: strikt besser oder geht auch gleich gut?
    public int betterThanLast(int i) {
        return lastD[i][numChoices - 1];
    }
}
